package yuchen.androidocr.imageUtil;

/**
 * Created by yuchen on 5/16/16.
 */
public class unionfind {

    private int[] id;
    private int count;
    private int[] sz;

    public unionfind(int n)
    {
        this.id = new int[n];
        this.count = n;
        this.sz = new int[n];
        int i;
        for(i = 0; i < this.count; i++)
        {
            this.id[i] = i;
            this.sz[i] = 1;
        }
    }

    public int find(int p)
    {
        while (p != this.id[p]){
            this.id[p] = this.id[this.id[p]];
            p = this.id[p];
        }
        return p;
    }

   public void union(int p, int q)
   {
       int i = this.find(p);
       int j = this.find(q);
       if(i == j){
           return;
       }
       if(this.sz[i] < this.sz[j]){
           this.id[i] = j;
           this.sz[j] += this.sz[i];
       }else{
           this.id[j] = i;
           this.sz[i] += this.sz[j];
       }
       this.count--;
   }

    public int[] getId() {
        return id;
    }

    public void setId(int[] id) {
        this.id = id;
    }
}
